package leetcode;

import java.util.HashMap;

/**
 * @Description 青蛙过河
 * @Author away
 * @Version V1.0.0
 * @Since 1.0
 * @Date 21.4.29
 */

public class T403 {

    Boolean[][] cache = null;
    public static void main(String[] args) {
        T403 t403 = new T403();
//        int[] stones = new int[]{0, 1, 3, 5, 6, 8, 12, 17};
//        int[] stones = new int[]{0, 2};
//        int[] stones = new int[]{0,1,2,3,4,8,9,11};
        int[] stones = new int[]{0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26,27,28,29,30,31,32,33,34,35,36,37,38,39,40,41,42,43,44,45,46,47,48,49,50,51,52,53,54,55,56,57,58,59,60,61,62,63,64,65,66,67,68,69,70,71,72,73,74,75,76,77,78,79,80,81,82,83,84,85,86,87,88,89,90,91,92,93,94,95,96,97,98,99,100,101,102,103,104,105,106,107,108,109,110,111,112,113,114,115,116,117,118,119,120,121,122,123,124,125,126,127,128,129,130,131,132,133,134,135,136,137,138,139,140,141,142,143,144,145,146,147,148,149,150,151,152,153,154,155,156,157,158,159,160,161,162,163,164,165,166,167,168,169,170,171,172};

        System.out.println(t403.canCross(stones));
        System.out.println(t403.map);
    }

    HashMap<String,Boolean> map = new HashMap();
    public boolean canCross(int[] stones) {

        //特殊值处理，第一次只能跳一步
        if (stones[1] - stones[0]>1) {
            return false;
        }
        return deepSearch(stones, 1, 1);
    }

    /**
     * 直接深搜超时
     * 加上缓存水过
     * @param stones
     * @param i      数组下标
     * @param k      当前下表可跳跃长度
     * @return
     */
    public boolean deepSearch(int[] stones, int i, int k) {
        String key = "" + i + "_" + k;

        if(map.get(key)!=null){
            return map.get(key);
        }
        if (i == stones.length - 1) {
            return true;
        }
        int minLength = stones[i + 1] - stones[i];
        if (minLength > k + 1) {
            return false;
        }
        boolean result = false;
        for (int j = i+1; j < stones.length; j++) {
            int tmp = stones[j] - stones[i];
            if (tmp == k - 1) {
                result |= deepSearch(stones, j, k - 1);
            } else if (tmp == k) {
                result |= deepSearch(stones, j, k);
            }else if (tmp == k+1){
                result |= deepSearch(stones, j, k+1);
            }else if(tmp >k +1){
                break;//剪枝
            }
        }
        map.put(key, result);
        return result;
    }

}
